/** 空闲的 */
const UNASSIGNED = 0;
/**
 * 回溯算法-数独解题器：目标是用数值1-9填满一个9*9的矩阵，要求
 * 每行和每列都由这九个数字构成。矩阵还包含了小方块（3*3矩阵），
 * 它们同样需要分别用这九个数字填满。谜题在开始给出一个已经填了一部分数字的矩阵。
 * @param grid 矩阵
 */
export function sudokuSolver(grid: number[][]): number[][] {
    if (solveSudoku(grid)) {
        return grid;
    } else {
        return undefined;
    }
}
const solveSudoku = (grid: number[][]) => {
    let row = 0;
    let col = 0;
    // 矩阵填满没有
    let checkBlankSpace = false;
    // 遍历矩阵，检查该矩阵是否填满了
    label: for (row = 0; row < grid.length; row ++) {
        for (col = 0; col < grid[row].length; col ++) {
            // 只要有一个空闲的，证明没有填满，就将checkBlankSpace置为true
            if (grid[row][col] === UNASSIGNED) {
                checkBlankSpace = true;
                break label;
            }
        }
    }
    // 填满了就直接返回
    if (!checkBlankSpace) {
        return true;
    }
    // 试着将1-9填入矩阵中
    for (let num = 1; num <= 9; num ++) {
        // 这一行还没有放入这个数，这一列还也没有放入这个数，这个3*3矩阵里也还没有放入这个数
        if (isSafe(grid, row, col, num)) {
            // 满足数独规则，那就暂时将这个数放入
            grid[row][col] = num;
            // 并再次执行solveSudoku，去下一个位置放一个新的数
            if (solveSudoku(grid)) {
                return true;
            }
            // 这个位置后面的位置放不了，那就回溯将这个位置清空，准备在这个位置放其他数
            grid[row][col] = UNASSIGNED;
        }
    }
    // 1-9这些数都不满足，就回溯
    return false;
};
/**
 * 将某个数填入到矩阵的这个位置是否满足数独规则
 * 1.这一行还没有放入这个数
 * 2.这一列还也没有放入这个数
 * 3.这个3*3矩阵里也还没有放入这个数
 * 那么这个位置就可以放入
 * @param grid 矩阵
 * @param row 横坐标
 * @param col 纵坐标
 * @param num 填入的是哪个树
 */
const isSafe = (grid: number[][], row: number, col: number, num: number) => {
    return (!usedInRow(grid, row, num) &&
            !usedInCol(grid, col, num) &&
            !usedInBox(grid, row, col, num));
};
/**
 * num是否在grid中的这一行row
 * @param grid 矩阵
 * @param row 目标行
 * @param num 当前数
 */
const usedInRow = (grid: number[][], row: number, num: number) => {
    // 遍历目标行的所有项
    for (let col = 0, gl = grid.length; col < gl; col ++) {
        // 目标行的所有项
        if (grid[row][col] === num) {
            return true;
        }
    }
    return false;
};
/**
 * num是否在grid中的这一列row
 * @param grid 矩阵
 * @param col 目标列
 * @param num 当前数
 */
const usedInCol = (grid: number[][], col: number, num: number) => {
    // 遍历目标列的所有项
    for (let row = 0, gl = grid.length; row < gl; row ++) {
        // 目标列的所有项
        if (grid[row][col] === num) {
            return true;
        }
    }
    return false;
};
const usedInBox = (grid: number[][], boxStartRow: number, boxStartCol: number, num: number) => {
    // 算出当前行所在的小矩阵，处于大矩阵的行索引
    boxStartRow = Math.floor(boxStartRow / 3);
    // 算出当前列所在的小矩阵，处于大矩阵的列索引
    boxStartCol = Math.floor(boxStartCol / 3);
    // 遍历3*3矩阵
    for (let row = 0; row < 3; row ++) {
        for (let col = 0; col < 3; col ++) {
            if (grid[boxStartRow * 3 + row][boxStartCol * 3 + col] === num) {
                return true;
            }
        }
    }
    return false;
};
